#include <stdio.h>
/**
 *
 * @return
 */
//考研初始只需完成setPartition即可，无需编写main函数
int setPartition(int a[],int n)
{
    int pivotkey,low=0,high=n-1,low0=0,high0=n-1,flag=1,k=n/2,i;
    int s1=0,s2=0;
    while (flag) //当low等于k-1时，也就是n/2-1时，分割结束
    {
        pivotkey=a[low]; //选择分割枢轴
        while (low<high) //基于枢轴对数据划分
        {
            while (low<high&&a[high]>=pivotkey)
                high--;
            if(low!=high)
                a[low]=a[high];
            while (low<high&&a[low]<=pivotkey)
                low++;
            if(low!=high)
                a[high]=a[low];
        }
        a[low]=pivotkey; //把分割值放到对应位置
        if(low==k-1)     //把枢轴是第n/2小元素，划分成功,数组下标是从0开始这里要减1
        {
            flag=0;
        }
        else{  //是否继续划分
            if(low<k-1)
            {
                low0=++low; //low0只是暂存，为下次使用准备，这里++low后，low比分隔值大1
                high=high0; //把上次暂存的high0拿过来
            } else{
                low=low0;  //把上次暂存的low0拿过来
                high0=--high; //high0只是暂存，为下次使用准备
            }
        }
    }
    for (i=0;i<k;i++)
    {
        printf("%3d",a[i]);
        s1+=a[i];
    }
    printf("\n");
    for (i=k;i<n;i++)
    {
        printf("%3d",a[i]);
        s2+=a[i];
    }
    printf("\n");
    return s2-s1;
}
int main() {
    int A[10]={4,1,12,18,7,13,18,16,2,15};
    int difference= setPartition(A,10);
    printf("%d\n",difference);
    return 0;
}
